﻿namespace AlgorithmInterview.Chapter02._02;

/// <summary>
/// 链表实现队列
/// </summary>
public class TestLNodeToQueue
{
    public class MyQueue<T>
    {
        class LNode<T>
        {
            public T Data;
            public LNode<T> Next;

            public LNode(T data)
            {
                this.Data = data; // 初始化队列大小
            }
        }

        private LNode<T> front; // 队列头
        private LNode<T> rear; // 队列尾
        private int num; // 队列元素个数

        public MyQueue()
        {
            // 初始时front,rear设置为null，num设置为0
            num = 0;
        }


        public int Count()
        {
            return this.num;
        }

        public void Clear()
        {
            front = rear = null;
        }

        public bool IsEmpty()
        {
            return (front == rear && num == 0);
        }

        // 入队
        public void Enqueue(T item)
        {
            LNode<T> q = new LNode<T>(item);
            if (rear == null) // 第一个元素入列时
            {
                front = rear = q;
            }
            else
            {
                // 把新元素挂到链尾
                rear.Next = q;
                // 修正rear指向为最后一个元素
                rear = q;
            }

            // 元素总数加1
            num++;
        }

        // 出队
        public T Dequeue()
        {
            if (IsEmpty())
            {
                Console.WriteLine("Queue is empty");
                return default(T);
            }

            // 取链首元素
            LNode<T> p = front;
            // 链头指向后移一位
            front = front.Next;
            // 如果此时链表为空，则同步修正rear
            if (front == null)
            {
                rear = null;
            }

            num--; // 个数-1
            return p.Data;
        }

        public T Peek()
        {
            if (IsEmpty())
            {
                Console.WriteLine("Queue is empty");
                return default(T);
            }

            return front.Data;
        }
    }
}